import java.util.Collection;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class IntCmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return  o1-o2;
    }
}
public class LeetCode {
    //优先级队列
    public ListNode mergeKLists1(ListNode[] lists) {
        //创建小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1,v2)->v1.val-v2.val);
        //加入元素
        for(ListNode l: lists){
            if(l!=null){
                heap.offer(l);
            }
        }
        //合并
        ListNode head = new ListNode(0);
        ListNode prev = head;
        while(!heap.isEmpty()){
            ListNode t = heap.poll();
            prev.next = t;
            prev = prev.next;
            if(t.next!=null){
                heap.offer(t.next);
            }
        }
        return head.next;
    }
    //递归
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length);
    }
    public ListNode merge(ListNode[] lists,int left,int right){
        if(left>right){
            return null;
        }
        if(left == right){
            return lists[left];
        }
        int mid = (right+left)/2;
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid+1,right);

        return TwoLists(l1,l2);
    }
    public ListNode TwoLists(ListNode l1,ListNode l2){
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode head = new ListNode(0);
        ListNode prev = head;
        ListNode cur1 = l1,cur2 = l2;
        while(cur1!=null&&cur2!=null){
            if(cur1.val<=cur2.val){
                prev.next = cur1;
                cur1 = cur1.next;
                prev = prev.next;
            }else{
                prev.next = cur2;
                cur2 = cur2.next;
                prev = prev.next;
            }
        }
        if(cur1!=null){
            prev.next = cur1;

        }
        if(cur2!=null){
            prev.next = cur2;

        }
        return head.next;
    }
}
